package com.duoduo.深度广度优先;

import com.duoduo.TreeNode;

/**
 * @program: 相同的树 100
 * @description: re
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 * @author: chaidl  ！
 * @create: 2022-03-02 14:17
 */
public class 相同的树 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 深度优先遍历，让两个根节点同步先序遍历
        return dfs(p, q);
    }


    private boolean dfs(TreeNode p, TreeNode q) {
        // 如果两个节点都为空,则返回true
        if (p == null && q == null) {
            return true;
        }
        // 如果两个节点都不为空，且值相同，则继续遍历子节点
        if (p != null && q != null) {
            if (p.val == q.val) {
                return dfs(p.left, q.left) && dfs(p.right, q.right);
            }
        }
        // 如果两个节点有一个为空，则直接返回false
        return false;
    }
}
